//https://leetcode.cn/problems/balanced-binary-tree/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

#include <stdlib.h>

//辅助函数，计算二叉树高度
int treeHeight(struct TreeNode* root){
    //空树
    if(root==NULL){
        return 0;
    }

    //叶子结点
    if(root->left==NULL && root->right==NULL){
        return 1;
    }

    int ret1=treeHeight(root->left);
    int ret2=treeHeight(root->right);

    return (ret1>ret2?ret1:ret2)+1;
}


//辅助函数，判断一根节点是否为平衡二叉树
bool __isBalanced(struct TreeNode* root) {
    //空树
    if(root==NULL){
        return true;
    }

    int leftHeight=treeHeight(root->left);
    int rightHeight=treeHeight(root->right);

   if(abs(leftHeight-rightHeight)>1){
        return false;
   }
   else{
        return true;
   }
}


 //问题原函数   
bool isBalanced(struct TreeNode* root) {
    if(root==NULL){
        return true;
    }
    
    if(__isBalanced(root)==false){
        return false;
    }

    return isBalanced(root->left) && isBalanced(root->right);
}


